package linkedlist;

//表示一个链表的节点
class Node{
    //节点保存的值
    public String value;
    //节点的下一个元素
    public Node next;

    public Node(String value){
        this.value = value;
        this.next = null;
    }
}
public class MyLinkedList {
    //把链表的头结点表示出来,此时整个链表就能获取到了
    //此处不包含傀儡节点,head == null的时候表示空的链表
    private Node head = null;
    //链表不需要用size记录元素的个数

    //插入元素
    //头插
    public void addFirst(String value){
        Node newNode = new Node(value);
        //创建一个新的节点
        newNode.next = head;
        //插到第一个元素的位置
        head = newNode;
        //现在newNode的位置成了第一个元素的位置,更新head
    }
    //尾插
    public void addLast(String value){
        //先找到尾巴,把新的节点,加到尾巴后面
        if(head == null){
            Node newNode = new Node(value);
            head = newNode;
            return;
        }
        Node tail = head;
        //注意,这里还需要考虑空链表直接尾插的问题,如果是空链表,tail就是null,根本就不会进入for循环
        // tail.next = newNode;就会报错,因此需要在前面加上一个特殊情况处理
        for( ;tail != null;tail = tail.next){
            if(tail.next == null){
                break;
            }
        }
        //这个循环跳出以后,tail就指向链表的尾巴了
        Node newNode = new Node(value);
        tail.next = newNode;
        newNode.next = null;
    }

    //指定下标位置插入
    public void add(int index,String value){
        //先来判断index是否合法
        //这里可以等于size,因为相当于尾插一个元素,其下标还是size,在工作中直接写一个size全局变量,
        // 每次add都size++,但在面试时需要写一个size()函数

        if(index < 0||index > size())
        {
            throw new RuntimeException("下标超出范围");
        }
        if(index == 0){
            addFirst(value);//能代码重用就重用,不要多写
            return;
        }
        Node newNode = new Node(value);
        //接着找到需要插入位置的前一个节点,将新的元素插入即可
        Node prev = head;
        for(int i = 0;i < index - 1;i++){
            prev = prev.next;
        }
        //这样就能够顺利的插入元素了,但是这个代码的关键在于特殊情况的处理,比如要在代码插到下标0处
        //这样for循环不会执行一次,相当一把元素插到了下标为1的地方
        newNode.next = prev.next;
        prev.next = newNode;

    }

    //写size函数
    public int size(){
        int size = 0;
        for(Node cur = head;cur != null;cur = cur.next){
            size++;
        }
        return size;
    }

    //判定某个元素是否在链表中包含
    public boolean contains(String value){
        for(Node cur = head;cur != null;cur = cur.next){
            if(cur.value.equals(value)){
                return true;
            }
        }
        return false;
    }

    //查找给定元素的下标
    public int indexOf(String value){
        int index = 0;
        for(Node cur = head;cur != null;cur = cur.next){
            if(cur.value.equals(value)){
                return index;
            }
            index++;
        }
        return -1;
    }

    //根据下标删除元素
    public void remove(int index){
        //这个链表为空没有什么影响,因为size()就为0,会直接捕捉到异常
        if(index < 0||index >= size()){
            throw new RuntimeException("下标超出范围");
        }
        if(index == 0){
            head = head.next;
            return;
        }
        //找到被删除的元素的第一个节点的位置,与按位置插入类似
        Node prev = head;
        for(int i = 0;i < index - 1;i++){
            prev = prev.next;
        }
        //修改了next引用之后,被删除的节点就没有引用再指向它,
        // 此时这个节点就会被Java的垃圾回收机制自动释放掉
        //如果是删除最后一个元素的话,也能正常执行,因为prev.next就变成了null
        prev.next = prev.next.next;
    }

    //根据元素值来删除元素
    public void remove(String value){
        //如果链表为空,直接结束方法
        Node prev = head;
        if(head.value.equals(value)){
            head = head.next;
            return;
        }
        for(;prev.next != null;prev = prev.next){
            if(prev.next.value.equals(value)){
                break;
            }
        }
        if(prev.next == null){
            return;
        }
        prev.next = prev.next.next;
    }

    //清空链表所有元素
    public void clear(){
        //直接修改head,head原来指向的所有的Node对象就没有引用了,都会被释放掉
        //1被释放,2就没人指向了,2被释放,进而3没人指向了,形成连锁反应,进而全部删除
        head = null;
    }

    @Override
    public String toString(){
        //遍历链表,形成一个字符串
        //遍历的时候,从头节点开始,进行一个一个元素的打印
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("[");
        for(Node cur = head;cur != null;cur = cur.next){
            stringBuilder.append(cur.value);
            if(cur.next != null){
                stringBuilder.append(",");
            }
        }
        stringBuilder.append("]");
        return stringBuilder.toString();
    }
    public static void test1(){
        MyLinkedList list = new MyLinkedList();
        list.addFirst("a");
        list.addFirst("b");
        list.addFirst("c");
        list.addFirst("d");
        System.out.println(list);//可以通过调试查看里面的指向情况
    }

    public static void test2(){
        MyLinkedList list = new MyLinkedList();
        list.addLast("a");
        System.out.println(list);
    }
    public static void test3(){
        MyLinkedList list = new MyLinkedList();
        list.add(0,"a");
        list.add(1,"b");
        list.add(2,"c");
        list.add(3,"d");
        list.add(0,"x");
        System.out.println(list.contains("a"));
//        System.out.println(list);
    }
    public static void test4() {
        MyLinkedList list = new MyLinkedList();
        list.add(0, "a");
        list.add(1, "b");
        list.add(2, "c");
        list.add(3, "d");
//        System.out.println(list.indexOf("d"));
//        list.remove(3);
        list.remove("a");
        System.out.println(list);
    }

    public static void main(String[] args) {
//        test1();
//        test2();
//        test3();
        test4();
    }
}
